// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ssa

import (
	"fmt"
	"math"
)

type indVarFlags uint8

const (
	indVarMinExc indVarFlags = 1 << iota // 最小值为独占（默认值：包含）
	indVarMaxInc                         // 最大值为独占（默认值：独占）
)

type indVar struct {
	ind   *Value // 诱导变量
	min   *Value // 最小值，包含/独占取决于标志
	max   *Value // 最大值，包含/独占取决于标志
	entry *Block // 循环中的输入块。
	flags indVarFlags
	// 不变量：对于严格由条目控制的所有块：
	// min<=ind<max[if flags==0]
	// min<ind<max[if flags==indVarMinExc]
	// min<=ind<=max[if flags==indVarMaxInc]
	// min<ind max[if flags==indVarMinExc]作为参数传递的SSA值是一个有效的归纳
}

// 变量，如果是，则提取：
// /*最小界限
// /*增量
// /*下一个值（每个循环中Phi进入归纳变量的SSA值）
// 目前，我们检测匹配的归纳变量（Phi min nxt），
// 其中nxt为（添加inc ind）。
// 如果不能正确解析归纳变量，则返回（nil，nil，nil）。
func parseIndVar(ind *Value) (min, inc, nxt *Value) {
	if ind.Op != OpPhi {
		return
	}

	if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
		min, nxt = ind.Args[1], n
	} else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
		min, nxt = ind.Args[0], n
	} else {
		// 不是公认的诱导变量。
		return
	}

	if nxt.Args[0] == ind { // nxt=ind+inc 
		inc = nxt.Args[1]
	} else if nxt.Args[1] == ind { // nxt=inc+ind 
		inc = nxt.Args[0]
	} else {
		panic("unreachable") // 上述情况中必须有一个是正确的。
	}

	return
}

// findIndVar在函数中查找归纳变量。
// 
// 查找满足以下条件的变量和块
// 
// 循环：
// ind=（Phi min nxt），如果ind<max 
// 那么进入循环
// 否则退出循环
// 
// 进入循环：
// 做点什么
// nxt=inc+ind 
// 进入循环
// 
// 退出循环：
func findIndVar(f *Func) []indVar {
	var iv []indVar
	sdom := f.Sdom()

	for _, b := range f.Blocks {
		if b.Kind != BlockIf || len(b.Preds) != 2 {
			continue
		}

		var flags indVarFlags
		var ind, max *Value // 归纳和最大

		// 检查控件是否为ind</=max或max>=ind。
		// TODO:处理32位比较。
		// TODO:处理未签名的比较？
		c := b.Controls[0]
		switch c.Op {
		case OpLeq64:
			flags |= indVarMaxInc
			fallthrough
		case OpLess64:
			ind, max = c.Args[0], c.Args[1]
		default:
			continue
		}

		// 看看这是否真的是一个归纳变量
		less := true
		min, inc, nxt := parseIndVar(ind)
		if min == nil {
			// 我们未能解析归纳变量。在下注之前，我们要检查
			// 控制运算是否用非惯用顺序的参数编写，
			// 因此我们相信being“max”（上限）实际上是归纳
			// 变量本身。对于像
			// for i:=0这样的代码，这种情况会发生；len（n）>i；i++
			min, inc, nxt = parseIndVar(max)
			if min == nil {
				// 两个操作数上都没有可识别的归纳变量
				continue
			}

			// 好的，参数已反转。交换它们，记住我们是
			// 在看一个ind>/>=循环（所以归纳必须是递减的）。
			ind, max = max, ind
			less = false
		}

		// 期望增量为非零常量。
		if inc.Op != OpConst64 {
			continue
		}
		step := inc.AuxInt
		if step == 0 {
			continue
		}

		// 增量符号必须与比较方向匹配。
		// 递增时，终止比较必须为ind</=max.
		// 递减时，终止比较必须为ind>/>=max.
		// 参见第26116期。
		if step > 0 && !less {
			continue
		}
		if step < 0 && less {
			continue
		}

		// 如果增量为负，则交换最小值/最大值及其标志
		if step < 0 {
			min, max = max, min
			oldf := flags
			flags = indVarMaxInc
			if oldf&indVarMaxInc == 0 {
				flags |= indVarMinExc
			}
			step = -step
		}

		// 到目前为止，我们提取了归纳变量（ind）、
		// 增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量增量。
		// 
		// 我们还知道ind的形式是（Phi min nxt），其中
		// nxt是（添加inc nxt），这意味着：1）inc支配nxt 
		// 和2）有一个从inc开始并包含nxt的循环。
		// 
		// 我们需要证明，只有当它小于最大值时，诱导变量才是递增的。
		// 必须满足以下两个条件才能接受ind 
		// 作为归纳变量。

		// 第一个条件：循环项有一个前置项，它是头块。这意味着b.Succs[0]是
		// ind<max时到达的。
		if len(b.Succs[0].b.Preds) != 1 {
			// b.Succs[1]必须退出循环。
			continue
		}

		// 第二个条件：b.Succs[0]控制nxt，因此当inc<max时，计算
		// nxt，这意味着nxt<=max。
		if !sdom.IsAncestorEq(b.Succs[0].b, nxt.Block) {
			// inc+ind只能通过进入循环的分支到达。
			continue
		}

		// 我们只能保证回路在感应变量
		// 的限制范围内运行，如果（其中一个）
		// （1）增量为±1 
		// （2）限制为常数
		// （3）回路的形式为k0，直到已知的负k，包括在内，步骤<=k 
		// （4）循环的形式为k0到已知非负-k独占，步骤<=k+1 
		// （5）循环的形式为已知非负到k0，minint+step<k0 
		if step > 1 {
			ok := false
			if min.Op == OpConst64 && max.Op == OpConst64 {
				if max.AuxInt > min.AuxInt && max.AuxInt%step == min.AuxInt%step { // 处理溢出
					ok = true
				}
			}
			// 处理这些形式的归纳变量。
			// KNN已知为非阴性。
			// 仅限带符号算术。（参见上面c上的开关）
			// KNN的可能性是len和cap；也许我们可以推断出其他人。
			// 对于i:=0；i<=KNN-k；i+=k 
			// 对于i:=0；i<KNN-（k-1）；i+=k 
			// 也处理递减。

			// “证据”复制自https:
			// 
			// 
			// 
			// L:=len（A）-PC 
			// i:=0；i<L；i=i+PC 
			// 
			// 我们知道：
			// 
			// 0+PC没有过流/下流。
			// len（A）-PC不溢出/下溢
			// L的最大值为MaxInt PC 
			// i<L<=MaxInt PC意味着i+PC<MaxInt，因此没有溢出。

			// 在SSA中匹配：
			// 如果（a）min.Op==OpConst64（k0）
			// 和（b）k0>=MININT+step 
			// 和（c）max.Op==OpSubtract（Op{StringLen SliceLen，SliceCap，k）
			// 或（c）max.Op==OpAdd（Op{StringLen，SliceLen SliceCap，SliceCap}-k）
			// 和（d）如果达到循环，则要求indVarMaxInc和step<=k或！indVarMaxInc和step-1<=k 

			if min.Op == OpConst64 && min.AuxInt >= step+math.MinInt64 {
				knn := max
				k := int64(0)
				var kArg *Value

				switch max.Op {
				case OpSub64:
					knn = max.Args[0]
					kArg = max.Args[1]

				case OpAdd64:
					knn = max.Args[0]
					kArg = max.Args[1]
					if knn.Op == OpConst64 {
						knn, kArg = kArg, knn
					}
				}
				switch knn.Op {
				case OpSliceLen, OpStringLen, OpSliceCap:
				default:
					knn = nil
				}

				if kArg != nil && kArg.Op == OpConst64 {
					k = kArg.AuxInt
					if max.Op == OpAdd64 {
						k = -k
					}
				}
				if k >= 0 && knn != nil {
					if inc.AuxInt > 0 { // 增加迭代
						// step和k之间的关系是为了确保iv永远不会超过knn 
						// 即iv<knn-（k-1）=>iv+k<=knn；iv<=knn-K=>iv+K<knn 
						if step <= k || flags&indVarMaxInc == 0 && step-1 == k {
							ok = true
						}
					} else { // 递减迭代
						// 将从最大值向最小值递减；max是knn-k；只有在
						// knn-k>[=]分钟时才会尝试递减；只有当最小步长不小于最小值时，下溢才是一个问题。
						// 这一切都假设有符号整数算法
						// 这已经通过上面的测试得到了保证：min.AuxInt>=step+math。MinInt64 
						ok = true
					}
				}
			}

			// TODO:其他展开习语
			// for i:=0；i<KNN-KNN%k；i+=k 
			// 对于i:=0；i<KNN&^（k-1）；i+=k 
			// 对于i:=0；i<KNN&-k；i+=k 

			if !ok {
				continue
			}
		}

		if f.pass.debug >= 1 {
			printIndVar(b, ind, min, max, step, flags)
		}

		iv = append(iv, indVar{
			ind:   ind,
			min:   min,
			max:   max,
			entry: b.Succs[0].b,
			flags: flags,
		})
		b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
	}

	return iv
}

func dropAdd64(v *Value) (*Value, int64) {
	if v.Op == OpAdd64 && v.Args[0].Op == OpConst64 {
		return v.Args[1], v.Args[0].AuxInt
	}
	if v.Op == OpAdd64 && v.Args[1].Op == OpConst64 {
		return v.Args[0], v.Args[1].AuxInt
	}
	return v, 0
}

func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
	mb1, mb2 := "[", "]"
	if flags&indVarMinExc != 0 {
		mb1 = "("
	}
	if flags&indVarMaxInc == 0 {
		mb2 = ")"
	}

	mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
	if !min.isGenericIntConst() {
		if b.Func.pass.debug >= 2 {
			mlim1 = fmt.Sprint(min)
		} else {
			mlim1 = "?"
		}
	}
	if !max.isGenericIntConst() {
		if b.Func.pass.debug >= 2 {
			mlim2 = fmt.Sprint(max)
		} else {
			mlim2 = "?"
		}
	}
	extra := ""
	if b.Func.pass.debug >= 2 {
		extra = fmt.Sprintf(" (%s)", i)
	}
	b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
}
